\section{Data Representation}
\label{sec:representation}

From the previous section, we introduced a fragmentation based on a data
structured called partial trees to represent a chunked XML document, providing
a good way for parallel XML processing. However, it is still a challenge to
develop a high-performance implementation based this data structure, especially
the concrete representation for it. For this purpose, we take two issues into
consideration as the following:

\textbf{Expressiveness} We use indexing (or labeling) to represent chunked XML
data so that it can be efficient to store them in databases~\cite{OOPC04},
exploiting its expressiveness to accelerate queries.

\textbf{Compactness} The indices for the XML data are stored in memory, so that the
expensive I/O cost for data exchanging are avoided.

The first design requirement relates to the efficiency of XML update. It is common that a
general-purpose framework may provide supports for updates, such as
ORDPATH~\cite{OOPC04}. However, such configuration tends to be expensive in case
of query-intensive(or only) scenario. Therefore, we focus only on update-free
case, i.e. we consider only queries with no update, making our framework much
faster and easier to implement. We expect that users are able to achieve their
objectives without updating, as long as appropriate programming interfaces 
over the framework are provided.

\input{fig-representation.tex}

We consider the second requirement as the functionality our designed indices can provide. 
One goal of this study is to support queries with order-aware ones such as
\texttt{following-sibling} and \texttt{following}. To achieve our goal, 
we define the following functions for processing queries on the given node $x$:
\begin{itemize}
\item Function $\mathsf{getChildren}(x)$ returns the children of $x$.
\item Function $\mathsf{getParent}(x)$ returns the parent of $x$.
\item Function $\mathsf{nextSibling}(x)$ returns the next sibling of $x$.
\item Function $\mathsf{prevSibling}(x)$ returns the previous sibling of $x$.
\item Function $\mathsf{isDescendant}(x, y)$ returns true if $x$ is a descendant of the node $y$.
\item Function $\mathsf{isFollowing}(x, y)$ returns true if $x$ is strictly after the node $y$ in terms of the document order.
\item Function $\mathsf{getNodesIn}(t, x)$ returns nodes with the tag $\mathit{t}$ in the subtree rooted at $x$.
\end{itemize}

For the implementation of the above functions, we designed two compact index 
sets, BFS-array (BFS stands for Breadth First Search, since nodes are arranged in BFS order) and Grouped-array, as shown in Figure~\ref{fig:2arrays}. For a single node, we design the 
following properties:
\begin{itemize}
	\item $\mathit{tag}$: the tag name of the node, short integers that map to the strings.
	\item $\mathit{type}$: the type of the node, including four node types as
	shown in Figure~\ref{fig:nodetypes}.
	\item $\mathit{st}$: the start position of the node, which is the position of 
	the tag in the original file to avoid global counting.
	\item $\mathit{ed}$: the end position.
\end{itemize}

With BFS and these two pointers, we are able to perform high-performance
functions $\mathsf{getChildren}$, $\mathsf{getParent}$, $\mathsf{nextSibling}$,
and $\mathsf{prevSibling}$. With \emph{Grouped-array}, we are allowed to
evaluate the function $\mathsf{getNodesIn}$ efficiently.

In this implementation, the two indexes totally take 
2 bytes for $\mathit{tag}$, 
1 bytes for $\mathit{type}$, 
8 bytes for $\mathit{st}$, 
8 bytes for $\mathit{ed}$, 
4 bytes for $\mathit{par}$, 
4 bytes for $\mathit{ch}$, and  
4 bytes for $\mathit{idx}$.
The sum of the above is merely $31$ bytes for representing an XML node. To the best
of our knowledge, it is smaller than the known existing implementations of DOM
trees or XML databases, and it is also the key to high-performance queries
executions.
